package abcut;

import java.io.BufferedReader;   
import java.io.FileInputStream;   
import java.io.FileNotFoundException;   
import java.io.IOException;   
import java.io.InputStreamReader;   
//主类，实现文件的读入与剪枝算法   
public class Search{   
    public static void main(String args[]){   
        try{   
            BufferedReader reader;   
            FileInputStream fi;   
            StringBuffer sb=new StringBuffer();   
            int p=0;   
            while((p=System.in.read())!=13){//从命令行读入文件名，暂存在一个字符串缓冲区，结束条件为读入回车   
                sb.append((char)p);   
            }   
            String name=new String(sb);//由字符串缓冲区中的字符序列新建一个字符串，代表读入的文件名   
            fi=new FileInputStream(name);   
            reader=new BufferedReader(new InputStreamReader(fi));   
            String str;    
            boolean flag=false;//判读是否开始读入最底层结点的值   
            int length=0;//记录读入行的字符串长度   
            NodeList nl=new NodeList();//存放结点的一个列表   
            Node start= new Node();//根结点   
            while((str=reader.readLine())!=null){//以行为单位读入   
                length=str.length();   
                StringBuffer ss=new StringBuffer(str);   
                StringBuffer sa=new StringBuffer("");   
                if(str.equals("VALUE")){//当读入的行为VALUE时，标记置为true，表示下一行开始读入最底层结点的值   
                    flag=true;   
                    continue;   
                }   
                if(str.equals("END")){//当读入行为END时，表示所有数据读入完毕，退出循环   
                    break;   
                }   
                if(flag){//若当期行开始是最底层结点的值   
                    StringBuffer s2=new StringBuffer("");   
                    int num=0;   
A:                  for(int i=0;i<length;i++){   
                        if(ss.charAt(i)!=' '&&ss.charAt(i)!='\t'){   
                            s2.append(ss.charAt(i));//读入对应结点的名字   
                        }   
                        else{   
                            num=i;   
                            break A;   
                        }   
                    }   
                    String last=new String(s2);   
                    boolean judge=false;   
                    int pos=0;   
                    StringBuffer val=new StringBuffer("");   
                    Node temp=new Node();   
B:                  for(int i=0;i<nl.size;i++){   
                        if(nl.get(i).name.equals(last)){   
                            for(int j=num;j<length;j++){   
                                if(ss.charAt(j)!=' '&&ss.charAt(j)!='\t'){   
                                    val.append(ss.charAt(j));//读入对应结点的值所代表的字符串   
                                }   
                            }   
                            pos=i;   
                            temp=nl.get(i);   
                            judge=true;//标记，表示找到结点   
                            break B;   
                        }   
                    }   
                    if(!judge){//未找到与所给结点名相同的结点，退出程序   
                        System.err.print("Node not found");   
                        System.exit(1);   
                    }   
                    int value=0;   
                    if(val.charAt(0)=='-'){//若值为负数   
                        int l=val.length();   
                        int count=1;   
                        for(int i=l-1;i>0;i--){   
                            value=value+((int)val.charAt(i)-48)*count;   
                            count=count*10;   
                        }   
                        value=-value;   
                        temp.data=value;   
                    }   
                    else{//值为正数   
                        int l=val.length();   
                        int count=1;   
                        for(int i=l-1;i>=0;i--){   
                            value=value+((int)val.charAt(i)-48)*count;   
                            count=count*10;   
                        }   
                        temp.data=value;//给该结点的data赋值为所读入的值   
                    }   
                    nl.replace(pos, temp);   
                }   
                else{//若不是读入最底层结点的值   
                    if(ss.charAt(0)=='R'&&ss.charAt(1)=='O'&&ss.charAt(2)=='O'&&ss.charAt(3)=='T'){//若为根结点   
C:                      for(int i=4;i<length;i++){   
                            if(ss.charAt(i)!=' '){   
                                for(int j=i;j<length;j++){   
                                    sa.append(ss.charAt(j));//读入根结点的名字   
                                }   
                                break C;   
                            }   
                        }   
                        String temp=new String(sa);   
                        start.name=temp;   
                        start.isMax=true;//根结点为极大结点   
                        nl.add(start);//加入列表   
                    }   
                    else{//若不是根结点   
                        StringBuffer s2=new StringBuffer("");   
                        int num=0;   
D:                      for(int i=0;i<length;i++){   
                            if(ss.charAt(i)!=' '&&ss.charAt(i)!='\t'){   
                                s2.append(ss.charAt(i));//读入作为父结点的结点名   
                            }   
                            else{   
                                num=i;   
                                break D;   
                            }   
                        }   
                        String father=new String(s2);   
                        Node fa=new Node();   
                        boolean judge=false;   
                        int pos=0;   
E:                      for(int i=0;i<nl.size;i++){//从列表中寻找该父结点   
                            if(nl.get(i).name.equals(father)){   
                                fa=nl.get(i);   
                                pos=i;   
                                judge=true;//标记，表明找到父结点   
                                break E;   
                            }   
                        }   
                        if(!judge){//若为找到父结点，则程序退出   
                            System.err.print("The father of the node not found");   
                            System.exit(1);   
                        }   
                        boolean in=false;//标记，判断是否得到子结点名   
                        for(int i=num;i<length-4;i++){   
                            StringBuffer son=new StringBuffer("");   
                            while(ss.charAt(i)!='\t'&&ss.charAt(i)!=' '){   
                                son.append(ss.charAt(i));//得到子结点名   
                                i++;   
                                in=true;   
                            }   
                            if(in){//若得到子结点名   
                                String so=new String(son);   
                                Node x=new Node(so);   
                                if(fa.isMax){//若其父结点为极大结点，则其为极小节点   
                                    x.isMax=false;   
                                }   
                                else{//否则，其为极大结点   
                                    x.isMax=true;   
                                }   
                                x.former=fa;//记录其父结点   
                                fa.son.add(x);//将其加入到其父结点的子结点列表中   
                                nl.add(x);//将新结点加入列表   
                                nl.replace(pos, fa);   
                                in=false;   
                            }      
                        }   
                    }   
                }   
            }   
            reader.close();//关闭流   
            Search se=new Search();   
            se.lookup(start);//开始搜索并剪枝   
            //输出最后根结点的情况   
            System.out.println("根节点："+start.name);   
            System.out.println("倒推值："+start.data);   
            System.out.println("应走的步骤："+start.next.name);   
        }catch(FileNotFoundException e){//异常处理   
            System.out.println("Catch "+e);   
        }catch(IOException i){//异常处理   
            System.out.println("Catch "+i);   
        }   
    }   
    //搜索及剪枝过程   
    public void lookup(Node p){   
        if(p.son.size!=0){//若当期结点的子结点个数不为0   
            for(int i=0;i<p.son.size;i++){//逐一递归搜索其子结点   
                if(p.son.get(i).isCut==false){//若子结点未被剪枝，则搜索该子结点   
                    lookup(p.son.get(i));   
                }   
            }   
        }   
        if(p.former==null){//当到达根结点时   
            if(p.son.size!=0){//若存在子结点   
                for(int i=0;i<p.son.size;i++){//则寻找与当期根结点的data相同的第一个子结点，将根结点的next赋为该子结点   
                    if(p.data==p.son.get(i).data){   
                        p.next=p.son.get(i);   
                        return;   
                    }   
                }   
            }   
            return;   
        }   
        else{//当没到达根结点时   
            if(p.former.data==-10000){//若当前结点的父结点未被赋值   
                p.former.data=p.data;//将其父结点的值赋为当期结点的值   
                Node temp=p.former;   
                if(p.former.son.size==1){//若其父结点仅有其一个子结点   
                    while(temp.son.size==1){//当结点仅包含一个子结点时   
                        if(temp.former!=null){//若父结点不为空   
                            if(temp.former.data!=-10000){//如果父结点已有值   
                                if(temp.former.isMax){//若父结点是极大结点   
                                    if(temp.former.data<temp.data){//取两者值中的最大值给父结点   
                                        temp.former.data=temp.data;    
                                    }      
                                }   
                                else{//若为极小节点   
                                    if(temp.former.data>temp.data){//取两者中的最小值给父结点   
                                        temp.former.data=temp.data;   
                                    }   
                                }   
                            }   
                            else{//若父结点没有值，则赋值为当期结点的值   
                                temp.former.data=temp.data;   
                            }   
                            temp=temp.former;//继续往前判断   
                        }   
                        else{//若父结点为空   
                            return;//返回   
                        }   
                    }   
                }   
                else{//若当前父结点含有多个子结点   
                    while(temp.former!=null){//若其父结点不为空   
                        if(temp.former.data==-10000){//若父结点未赋过值，则继续向祖先结点搜索   
                            temp=temp.former;   
                            continue;   
                        }   
                        else{//若其父结点赋过值   
                            if(p.former.isMax){//若当前检查结点的父结点是极大结点   
                                if(!temp.former.isMax){//且其当前祖先结点是极小节点   
                                    if(p.former.data>=temp.former.data){//若α>=β,则β剪枝   
                                        p.former.cut(p);   
                                        p.former.next=p;   
                                        break;//跳出循环   
                                    }   
                                }   
                            }   
                            else{//若当前检查结点的父结点为极小节点   
                                if(temp.former.isMax){//且当前祖先结点为极大结点   
                                    if(p.former.data==temp.former.data){//若β=α,则α剪枝
                                        p.former.cut(p);   
                                        p.former.next=p;   
                                        break;//跳出循环   
                                    }   
                                }   
                            }   
                        }   
                        temp=temp.former;//继续往前搜索   
                    }   
                }   
            }   
            else{//若当前结点的父结点已经被赋值   
                Node temp=p.former;   
                if(p.former.isMax){//若父结点为极大结点   
                    if(p.former.data<p.data){//赋为两者中的最大值   
                        p.former.data=p.data;   
                    }      
                }   
                else{//若父结点为极小节点   
                    if(p.former.data>p.data){//赋为两者中的最小值   
                        p.former.data=p.data;   
                    }   
                }   
                while(temp.former!=null){//当祖先结点不为空时   
                    if(temp.former.data==-10000){//若祖先结点未被赋值，则继续往前搜索   
                        temp=temp.former;   
                        continue;   
                    }   
                    else{//若祖先结点有值   
                        if(p.former.isMax){//当前结点的父结点为极大结点   
                            if(!temp.former.isMax){//且当前祖先结点为极小节点   
                                if(p.former.data>=temp.former.data){//若α>=β则β剪枝   
                                    p.former.cut(p);   
                                    p.former.next=p;   
                                    break;//跳出循环   
                                }      
                            }   
                        }   
                        else{//当前结点的父结点为极小节点   
                            if(temp.former.isMax){//且当前祖先结点为极大结点   
                                if(p.former.data==temp.former.data){//若β=α则α剪枝
                                    p.former.cut(p);   
                                    p.former.next=p;   
                                    break;//跳出循环   
                                }   
                            }   
                        }   
                    }   
                    temp=temp.former;//继续往前搜索   
                }   
                return;//返回   
            }   
        }   
    }   
} 